---
title: "6、统计子矩阵"
created: 2025-11-28
tags:
  - 算法
---

# 6、统计子矩阵

## 题目 [统计子矩阵](https://www.lanqiao.cn/problems/2109/learning/)

![[image-00f7d1e8.png]]

## 思路分析

二维前缀和

没有固定方块大小 所以可能得每个长宽都枚举

得四重循环 一定会超时

但是一时半会确实没想到可优化的点

另外 k有18位 得用long long

## 代码实现

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=510;

LL a[N][N],s[N][N];

int main()

{

  int n,m,k;

  cin>>n>>m>>k;

  for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

      cin>>a[i][j];

      s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

    }

  }

  LL cnt=0;

  for(int x1=1;x1<=n;x1++){

    for(int y1=1;y1<=m;y1++){

      for(int x2=x1;x2<=n;x2++){

        for(int y2=y1;y2<=m;y2++){

          int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];

          if(sum<=k)

            cnt++;

        }

      }

    }

  }

  cout<<cnt;

  return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[5、X进制减法|5、X进制减法]] 🏠 [[00-刷题理模型]] ➡️ [[7、积木画|7、积木画]]